package org.example.Soution003;

import java.util.ArrayDeque;
import java.util.Deque;

public class StackMaxRecArea {
    public static void main(String[] args) {
        StackMaxRecArea stackMaxRecArea = new StackMaxRecArea();
        System.out.println(stackMaxRecArea.largestRectangleArea(new int[] { 2,1,5,6,2,3}));
    }


//    public int largestRectangleArea(int[] heights) {
//        int len=heights.length;
//        int res=0;
//
//        //边界
//        if(len==0) return 0;
//        if(len==1) return heights[0];
//
//        //正常建栈做
//        Deque<Integer> stack=new ArrayDeque<Integer>();
//        for(int i=0;i<len;i++){
//            while(!stack.isEmpty() && heights[stack.peek()]>heights[i]){
//                int curHeight=heights[stack.pop()];
//                while(!stack.isEmpty() && heights[stack.peek()]==curHeight){
//                    stack.pop();
//                }
//                int curLength=0;
//                if(stack.isEmpty()) curLength=i;
//                else curLength=i-stack.peek()-1;
//                res=Math.max(res,curLength*curHeight);
//            }
//            stack.push(i);
//        }
//
//        //这样以后剩下的只会是单调栈
//        while(!stack.isEmpty()){
//            int curHeight=heights[stack.pop()];
//            int curLength=0;
//            if(stack.isEmpty()) curLength=len;
//            else curLength=len-stack.peek()-1;
//            res=Math.max(res,curLength*curHeight);
//        }
//        return res;
//    }

    //哨兵模式，不用判空了
    public int largestRectangleArea(int[] heights) {
        int len=heights.length;
        int res=0;

        //边界
        if(len==0) return 0;
        if(len==1) return heights[0];

        //添加哨兵
        int[] newHeights=new int[len+2];
        newHeights[0]=0;
        System.arraycopy(heights,0,newHeights,1,len);
        newHeights[len+1]=0;
        len+=2;

        //正常建栈做
        Deque<Integer> stack=new ArrayDeque<Integer>();
        stack.push(0);
        for(int i=1;i<len;i++){
            while(!stack.isEmpty() && newHeights[stack.peek()]>newHeights[i]){
                int curHeight=newHeights[stack.pop()];
                while(!stack.isEmpty() && newHeights[stack.peek()]==curHeight){
                    stack.pop();
                }
                int curLength=0;
                if(stack.isEmpty()) curLength=i;
                else curLength=i-stack.peek()-1;
                res=Math.max(res,curLength*curHeight);
            }
            stack.push(i);
        }
        return res;
    }
}
